package backTrack;

import java.util.*;

public class ds93 {
    public static void main(String[] args) {
        System.out.println(restoreIpAddresses("25525511135"));
    }
    static List<String> path = new ArrayList<>();
    public static List<String> restoreIpAddresses(String s) {
        List<String> ans = new ArrayList<>();
        dfs(s,0, ans);
        return ans;
    }
    public static void dfs(String s, int index, List<String> ans){
        if(path.size() > 4 || index > s.length())
            return;
        if(path.size() == 4 && index == s.length()){
            StringBuilder stringBuilder = new StringBuilder();
            for (String s1 : path) {
                stringBuilder.append(s1);
                stringBuilder.append(".");
            }
            ans.add(stringBuilder.substring(0, stringBuilder.length() - 1));
            return;
        }
        for (int i = index; i < s.length(); i++) {
            if(isValid(s.substring(index, i + 1))){
                path.add(s.substring(index, i + 1));
            }
            else continue;
            dfs(s, i + 1, ans);
            path.remove(path.size() - 1);
        }
    }
    public static boolean isValid(String s){
        if((s.length() > 1 && s.charAt(0) == '0') || (s.length() > 3))
            return false;
        int value = Integer.parseInt(s);
        if(value > 255 || value < 0)
            return false;
        return true;
    }
}
